package com.二叉树2;

import java.util.*;

public class 最低公共节点 {
   static class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            // Stack for tree traversal
            Deque<TreeNode> stack = new ArrayDeque<>();

            // HashMap for parent pointers
            Map<TreeNode, TreeNode> parent = new HashMap<>();

            parent.put(root, null);
            stack.push(root);

            // Iterate until we find both the nodes p and q
            while (!parent.containsKey(p) || !parent.containsKey(q)) {

                TreeNode node = stack.pop();

                // While traversing the tree, keep saving the parent pointers.
                if (node.left != null) {
                    parent.put(node.left, node);
                    stack.push(node.left);
                }
                if (node.right != null) {
                    parent.put(node.right, node);
                    stack.push(node.right);
                }
            }

            // Ancestors set() for node p.
            Set<TreeNode> ancestors = new HashSet<>();

            // Process all ancestors for node p using parent pointers.
            while (p != null) {
                ancestors.add(p);
                p = parent.get(p);
            }

            // The first ancestor of q which appears in
            // p's ancestor set() is their lowest common ancestor.
            while (!ancestors.contains(q))
                q = parent.get(q);
            return q;

        }
       public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q){
            if(root == null){
                return null;
            }
            Map<TreeNode ,TreeNode> map = new HashMap<>();
           Stack<TreeNode> stack = new Stack<>();
           stack.push(root);
           map.put(root,null);
           while (!map.containsKey(p) || !map.containsKey(q)){
               TreeNode tmp = stack.pop();
               if(tmp.left != null){
                   stack.push(tmp.left);
                   map.put(tmp.left,tmp);
               }
               if(tmp.right != null){
                   stack.push(tmp.right);
                   map.put(tmp.right,tmp);
               }
           }
           Set<TreeNode> set = new HashSet<>();
           while (p != null){
               set.add(p);
               p = map.get(p);
           }
           while (!set.contains(q)){
               q = map.get(q);
           }

           return q;
       }

       public static void main(String[] args) {
           Solution  solution = new Solution();
           TreeNode root = new TreeNode(new int[]{1, 2, 3,4,5,6,7});
           TreeNode p = root.left.left;
           TreeNode q = root.right.right;
           TreeNode treeNode = solution.lowestCommonAncestor2(root, p, q);
       }
    }

}
